import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * 剑指 offer 2 088 爬楼梯的最少成本
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
 * <p>
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 * <p>
 * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 */
public class MinCostClimbingStairs {

    @Test
    public void test1() {
        Assertions.assertEquals(15, minCostClimbingStairs2(new int[]{10, 15, 20}));
    }

    @Test
    public void test2() {
        Assertions.assertEquals(6, minCostClimbingStairs2(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }

    @Test
    public void test3() {
        Assertions.assertEquals(15, minCostClimbingStairs2(new int[]{10, 15, 20}));
    }

    int[] cost;
    int[] cache;
    int cacheHitCount;


    /**
     * 方式二：非递归
     *
     * @param cost
     * @return
     */
    public int minCostClimbingStairs2(int[] cost) {
//      缓存的长度必须是 n + 1，因为总共有n级别台阶，但是要走到第n+1级台阶才算走过了终点
        cache = new int[cost.length + 1];
//        在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
//        开始的两个台阶都是不需要cost的
        cache[0] = cache[1] = 0;

        for (int i = 2; i < cache.length; i++) {
//            比较谁可以用最少的体力走最远的路（台阶）
            cache[i] = Math.min(
//                    第i-2级 之前的台阶的花费 + 第 i - 2 级台阶的花费
                    cache[i - 2] + cost[i - 2],
//                    第i-1级 之前的台阶的花费 + 第 i - 1 级台阶的花费
                    cache[i - 1] + cost[i - 1]
            );
        }

        return cache[cache.length - 1];

    }

    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        cacheHitCount = 0;
        cache = new int[cost.length];
        Arrays.fill(cache, -1);
        int result = Math.min(find(0), find(1));
        System.out.println("缓存命中 " + cacheHitCount);
        return result;
    }

    private int find(int index) {

        if (index == cost.length) {
            return 0;
        } else if (index > cost.length) {
            return Integer.MAX_VALUE;
        }

        if (cache[index] != -1) {
            cacheHitCount++;
            return cache[index];
        }

        int oneStepCost = find(index + 1);
        int twoStepCost = find(index + 2);

        return cache[index] = cost[index] + Math.min(oneStepCost, twoStepCost);

    }
}
